/**
 * 迭代 - 镜像二叉树
 */
#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right) {}
};

class Solution {
public:
    /**
     * 重复计算了两次。。。
     */
    bool check(TreeNode *u, TreeNode *v) {
        queue<TreeNode *> q;
        q.push(u);
        q.push(v);
        int size = 0;
        while (!q.empty()) {
            u = q.front();
            q.pop();
            v = q.front();
            q.pop();
            if (!u && !v) continue;  // 两个都为空
            if ((!u || !v) || (u->val != v->val))
                return false;  // 一个为空或者值不相等

            q.push(u->left);
            q.push(v->right);

            q.push(u->right);
            q.push(v->left);
            if (q.size() > size) {
                size = q.size();
            }
        }
        cout << size << endl;
        return true;
    }

    bool isSymmetric(TreeNode *root) { return check(root, root); }
};

int main() {
    Solution s;

    // 一号树
    TreeNode *tree1 = new TreeNode(1);
    tree1->left = new TreeNode(5);
    tree1->right = new TreeNode(2);
    tree1->right->left = new TreeNode(3);
    cout << s.isSymmetric(tree1) << endl;

    // 二号树
    TreeNode *tree2 = new TreeNode(1);
    tree2->left = new TreeNode(2);
    tree2->right = new TreeNode(2);
    tree2->left->right = new TreeNode(3);
    tree2->right->left = new TreeNode(3);
    cout << s.isSymmetric(tree2) << endl;

    return 0;
}